package heap;

/**
 * 创建一个堆
 * @author le
 * */
public class CreateBigHeap
{
    public static void main(String[] args)
    {
        int[] res = {5, 2, 9, 4, 7, 6, 1, 3, 8};
        int size = res.length;

        for (int i = size/2 ; i >= 0;i--){
            heapify(res,i,size);
        }
        for (int s : res){
            System.out.println(s);
        }
    }

    /**
     * 交换数组中的两个元素
     * @param a 交换的数组
     * @param i 第一个交换元素的索引
     * @param j 第二个交换元素的索引
     */
    private static void swap(int[] a,int i,int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    /**
     * 堆化数组
     * @param a
     * @param i
     * @param size 数组的长度
     */
    private static void heapify(int[] a, int i, int size){
        int left = 2*i + 1;
        int right = 2*i + 2;
        int max = i;

        if (left < size && a[left] > a[max]){
            max = left;
        }
        if (right < size && a[right] > a[max]){
            max = right;
        }
        if (max != i){
            swap(a, i, max);
            heapify(a, max, size);
        }
    }
}
